import java.util.ArrayList;
import java.util.List;

class MorrispreorderTraversal {
    //个人理解Morris的思想就是借助树的空闲指针将树链表化
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        while(root != null){
            //前序遍历添加根节点
            res.add(root.val);
            //左子树不为空，按照前序遍历规则先遍历左子树
            //遍历前先将左子树在前序遍历的最后一个节点指向根节点的右子树。
            //前序遍历的最后一个节点：1、是叶节点，2、优先右子树，如果没有右子树再找左子树
            if(root.left != null){
                TreeNode precessor = root.left;
                //1、是叶节点才终止循环
                while(precessor.right != null || precessor.left != null){
                    //2、优先右子树，如果没有右子树再找左子树
                    if(precessor.right != null){
                        precessor = precessor.right;
                    }else{
                        precessor = precessor.left;
                    }
                }
                //最后一个节点指向根节点的右子树
                precessor.right = root.right;
                //先遍历左子树
                root = root.left;
            }else{
                //左子树为空，按照前序遍历规则遍历右子树。
                root = root.right;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode cur1=new TreeNode(1);
        TreeNode cur2=new TreeNode(2);
        TreeNode cur3=new TreeNode(3);
        TreeNode cur4=new TreeNode(4);
        cur1.left=cur2;
        cur2.left=cur3;
        cur1.right=cur4;
        MorrispreorderTraversal solution=new MorrispreorderTraversal();

        List<Integer> ret=solution.preorderTraversal(cur1);
        for(int i:ret){
            System.out.println(i+" ");
        }

    }
}